package dp;

/**
 * @author pengfei.hpf
 * @date 2020/2/10
 * @verdion 1.0.0
 * Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num Calculate the number of 1's in their binary representation and return them as an array.
 *
 * Example 1:
 *
 * Input: 2
 * Output: [0,1,1]
 * Example 2:
 *
 * Input: 5
 * Output: [0,1,1,2,1,2]
 * Follow up:
 *
 * It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
 * Space complexity should be O(n).
 * Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/counting-bits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CountBits {
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        res[0] = 0;
        if(num == 0){
            return res;
        }
        res[1] = 1;
        int curIndex = 2;
        int target = 2;
        int i = 0;
        while(curIndex <= num){
            if( curIndex == target){
                target *= 2;
                i = 0;
            }
            res[curIndex] = res[i] + 1;
            i ++;
            curIndex ++;
        }
        return res;
    }
}
